package arithmetic.fibonacci;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhangzg
 * @date 2022/10/9
 * 斐波那契数列:
 * f(0)=0
 * f(1)=1
 * f(n)=f(n-2)+f(n-1)
 */
public class Test {

    private static Map<Integer,Integer> map=new HashMap<Integer,Integer>();

    public static void main(String[] args) {
        System.out.println(calc(7));
        System.out.println(calc1(7));
    }

    public static int calc(int n){
        if (n==0) return 0;
        if (n==1) return 1;
        if (map.get(n) !=null){
            return map.get(n);
        }else {
            int result=calc(n-1)+calc(n-2);
            map.put(n,result);
            return result;
        }
    }

    public static int calc1(int n){
        if (n==0) return 0;
        if (n==1) return 1;
        int result=0;
        int pre=1;
        int prePre=0;
        for (int i=2;i<=n;i++){
            result=pre+prePre;
            prePre=pre;
            pre=result;
        }
        return result;
    }

}
